\section{The Algorithm}
In this section we describe our main algorithm {\sc
GlobalShadowMatching} (\cf, Algorithm~\ref{alg:shadow_algorithm}).
This algorithm is a nontrivial extension of Zelke's
algorithm~\cite{Zelke08}. The basic idea of this algorithm (and all
previous algorithms) is to add an edge to the matching only when it
is ``big'' enough.
%

The main procedure in previous algorithms has been to maintain a
matching, and try to make {\it local} improvements to it, as new
edges arrive in the stream. This is the central idea in
McGregor~\cite{McGregor05}. A matching is maintained, and the next
edge in the stream was added to the matching if its weight was
``sufficiently'' greater than the edge(s) it would replace. A key
ingredient in Zelke's algorithm, which is the new idea over
McGregor's,  is to store some previously deleted edges, called
\textit{shadow-edges}. Whenever a new edge in the stream arrives,
the algorithm adds it, and some stored previously deleted edges, if
their total weight is ``sufficiently'' greater than all the edges
they would together replace. This is still a local algorithm in the
sense that the deleted edges considered are always in the near
neighborhood of the input stream edge. Our algorithm goes one step
further in looking for global improvements by considering long
alternating paths of currently matched edges and previously deleted
edges.

Here is some notation, borrowed from Zelke's paper that we also use.
For any edge $uv$ currently in the matching, shadow-edge($uv, v$) is
the edge incident to $v$ that was deleted when $uv$ was added to the
matching; similarly shadow-edge($uv, u$). So for every edge
currently in the matching, the algorithm maintains (at most) two
other edges which could reappear in the matching at a later stage.
When an edge $e$ arrives in the stream, the algorithm tries to add
edge $e$ at the cost of removing some edges currently in the
matching, but perhaps bringing back some shadow-edges. Such
local-improvement algorithms turn out to be effective only if the
local improvements are ``substantial''; that is, the local weight
improves by a factor of at least $\gamma > 1$. For a more detailed
explanation of the algorithm, we refer the reader to~\cite{Zelke08}.

%Our algorithm uses the same general technique of Zelke. Certain deleted edges are maintained in the hope that they can reappear and improve the matching. However, a key difference is that we look for {\em global} improvements, when new edges arrive. Rather than looking at the neighboring edges in matching or their shadows, we look for long alternating paths. Our algorithm then augments shadow edges on this path by deleting the current matching edges if this results in substantial improvement. While this requires a greater update time with every stream element, we are able to prove a better approximation ratio.
%%Apart from the fact that we look for global improvements to the matching, our algorithm is essentially the same as Zelke's.
%There is another minor difference in that if the arriving edge is a multi-edge of an edge currently in the matching, then we replace the existing edge as long
%as the new edge has higher weight (disregarding the $\gamma$ factor).

%We make some key simplifying assumptions on the input graph that help us simplify the analysis. We also follow a charging scheme.
%
%However, our analysis follows a different approach.  Our algorithm has two minor differences from Zelke's. We only
%consider local improvements that would insert the new edge $e$ (this
%helps simplify our analysis and prove a stronger bound); this
%condition is in line~\ref{alg:change_part}. Zelke's algorithm, on
%the other hand, may end up making a local adjustment to the matching
%in the neighborhood of the new edge, even if the new edge did not
%get added by this local improvement. The second difference in our
%algorithm is that, if the arriving edge is a multi-edge of an edge
%currently in the matching, then we replace the existing edge as long
%as the new edge has higher weight (disregarding the $\gamma$
%factor). Neither of these changes seem to make Zelke's algorithm
%``better'' at an intuitive level. Yet, these changes are crucial in
%simplifying our analysis.

We now describe the formal algorithm in {\sc GlobalShadowMatching}
(cf. Algorithm~\ref{alg:shadow_algorithm}). The algorithm proceeds
by storing a current matching and certain shadow edges. When a new
edge $e$ appears in the stream, all \textit{alternating paths}
consisting of alternating matched and shadow edges (including $e$)
are considered. More precisely, for any edge $e=y_1y_2$ drawn from
the stream, consider any path consisting of matching edges $y_1b_1$
and $y_2d_1$ adjacent to $e$, shadow edges
$b_1a_2$=shadow-edge($y_1b_1$, $b_1$) and
$d_1c_2$=shadow-edge($y_2d_1$, $d_1$), matching edges adjacent to
these shadow edges $b_1a_2$ and $d_1c_2$, their shadow edges, and so
on. \textit{Alternating paths} are those paths whose both end edges
are in the matching. (See Figure~\ref{fig:algo}).
%
Notice that these paths are well defined, since each edge can have
at most one shadow edge on each side, and each vertex can have at
most one edge incident to it that is currently in the matching. The
algorithm looks for an alternating path where the weight of shadow
edges plus the weight of $e$ exceed by a $\gamma$-factor the weight
of all the currently matched edges that would be deleted if these
are added. If no such path is found, then $e$ is thrown away. If one
is found, we use the \textit{minimal} one, denoted by $Q$, where the
minimal alternating path corresponding to a parameter $\gamma$ can
be formally defined as follows.
%
%Before describing the algorithm, we need to introduce a definition.
%
\begin{definition}[Minimal $\gamma$-Alternating
Path]\label{def:minimal_alternating_path}
%Minimal Alternating Path:
A $\gamma$-alternating path $Q$ is an alternating path such that the
sum of weights of the matched edges in $Q$ is at most $1/\gamma$
fraction of the sum of weights of the remaining edges in $Q$.
%
Further, we say that $Q$ is a minimal $\gamma$-alternating path if
every of its sub-paths $Q'\neq Q$ containing $e$ is not
$\gamma$-alternating.
%Further, a minimal $\gamma$-alternating path $Q$
%is a $\gamma$-alternating path $Q$ such that for every sub-path $Q'$
%of $Q$ where $Q'$ is an alternating path (that includes the new
%edge), and $Q' \neq Q$,
%%and $Q$ is an alternating path,
%%(i.e. $Q$ is an alternating path of matched edges and shadow edges in $P$),
%the sum of weights of the matched edges in $Q'$ is more than
%$1/\gamma$ fraction of the sum of weights of the remaining edges in
%$Q'$.
%shadow edges and the new edge in $Q$ is less than
%$\gamma$ times the sum of weights of matched edges in $Q$.
%Finally, the minimal alternating path should end with matched edges at both
%ends.
\end{definition}

Such a minimal $\gamma$-alternating path $Q$ can be found naively in
$O(n^2)$ steps but it is not hard to improve this to $O(n)$.

A possible algorithm would be to just flip all the edges in $Q$ to
turn currently matched edges into shadow edges and vice versa;
however, this faces a technical difficulty in that a certain
desirable local property is not maintained (details can be found in
the next section).
%
Therefore, the algorithm searches for better options: Let the
matched edges at the ends of the path $Q$ be denoted by $(a_k,b_k)$
and $(c_{k'},d_{k'})$. Starting from both these edges, the algorithm
tries to find two {\em sub-paths} of $Q$ such that on either
sub-path, the weight of the shadow-edges still exceeds the weight of
the corresponding matched edges adjacent to them by a
$\gamma$-factor.
%
% (here if the sub-path length is $(2l+1)$, it
%contains the first $l$ shadow edges and the $(l+1)$ matched edges
%adjacent to them). The minimality of $Q$ ensures
%an additional desired local property: the first $t$ matched edges (starting from $(a_k,b_k)$ or
%$(c_{k'},d_{k'})$), for all $t\leq l$, have weight at most
%$1/\gamma$ times the weight of the first $t$ shadow edges.
%
If there is such a sub-path from both $(a_k,b_k)$ and
$(c_{k'},d_{k'})$, neither of which includes $e$, then the smallest
such paths are called $Q_1$ and $Q_2$ respectively.
%
%(Notice that if one of the sub-paths needs to include $e$ to exceed
%by a $\gamma$-factor, then it must include the entire path $Q$ -
%this follows from the minimality of $Q$.)
In this case, the algorithm flips the matched and shadow edges in
$Q_1$ and $Q_2$ to obtain the new matching (and $e$ is thrown away).
If either $Q_1$ or $Q_2$ does not exist, then all of $Q$ is flipped.
The reason why we need to check for $Q_1$ and $Q_2$ before flipping
$Q$ will be clear in proof of Lemma~\ref{lem:charge_eating}.

%A few comments about the algorithm:
%\begin{itemize}
%\item In Line~\ref{alg:longpath} notice that $S$ is well defined, since each edge can have at most one shadow edge, and each vertex can have at most one edge incident on it that is currently in the matching.
%\item
%In Line~\ref{alg:minimal} recall our definition of minimal alternating path. We also include the fact that the edges to be augmented have a weight at least $\gamma$ times the weight of edges to be deleted. With respect to Line~\ref{alg:change_part} we make two comments. Notice that there cannot be such a path starting at $a_1$ and going beyond $y_1$ and yet stopping before $c_1$ as this would violate the minimality property of the initially chosen alternating path $A$.

%The above steps can be done naively in $O(n^2)$ steps. These can in fact be improved to $O(n)$ steps using fairly simple ideas that we do not describe here so
%
Our algorithm needs an update time of $O(n)$ compared to $O(1)$
update time of previous algorithms. It is easy to see that our
algorithm (as also the previous ones) requires $O(n\polylog{n})$
space. This is because the algorithm stores at most a linear number
of edges.

\begin{algorithm}[t]
\caption{\sc GlobalShadowMatching($G$, $\gamma$)} \label{alg:shadow_algorithm}%
%{\bf Input:} Graph $G$ and a parameter $\gamma$\\
%{\bf Output: } Matching $M$ on $G$ such that the weight of $G$ is at
%least $1/\rho$ times the weight of the maximum weight matching where
%$\rho$ is defined in lemma~\ref{lem:zelke}.%
\begin{algorithmic}[1]
\small
\STATE $M:=\emptyset$ %

\WHILE{input stream is not empty}%

\STATE get next input edge $e=y_1y_2$

\STATE \textbf{if} there is a multiple edge $e'=y_1y_2$ in $M$
\textbf{then} replace $e'$ by $e$ if $w(e)>w(e')$ and skip to the
next input.\label{line:multiple_edge}

%\STATE Let $g_1y_1$, $g_2y_2$ be the edges of $M$ sharing a vertex
%with $y_1y_2$. $a_1g_1$ := shadow-edge($g1y1$, $g1$) and $a_2g_2$ :=
%shadow-edge($g2y2$, $g2$). Let $a_1c_1$ be the edge of $M$ covering vertex $a_1$ and
%$a_2c_2$ be the edge of $M$ covering vertex $a_2$ and so on.

%\STATE $S := \{y_1y_2, g_1y_1, a_1g_1, a_1c_1, g_2y_2, a_2g_2, a_2c_2\}$

\STATE Let $a_1=y_1$ and $c_1=y_2$. Consider a path
%$P := \{y_1y_2,
%a_1b_1, c_1d_1, b_1a_2, d_1c_2, a_2b_2, c_2d_2, b_2a_3, d_2c_3,
%\ldots \}$
$P:=\{y_1y_2\}\cup \{a_1b_1, b_1a_2, a_2b_2, \ldots\} \cup \{c_1d_1,
d_1c_2, c_2d_2, \ldots\}$ consisting of the alternating path
alternating between edges currently in the matching (i.e. $a_1b_1,
a_2b_2, \ldots$ and $c_1d_1, c_2d_2, \ldots$), and shadow edges
(i.e. $b_1a_2, b_2a_3, \ldots$ and $d_1c_2, d_2c_3, \ldots$).  See
Figure~\ref{fig:algo}. \label{alg:longpath}

%\COMMENT{Notice that $S$ is well defined, since each edge can have at most one shadow edge, and each vertex can have at most one edge incident on it that is currently in the matching. }

%\STATE Find an augmenting set $A\subset S$ containing $y_1y_2$ that
%maximizes $r(A) := w(A) - \gamma \cdot w(M(A))$

\STATE \label{alg:minimal} Find any minimal $\gamma$-alternating
path $Q\subset P$ containing $y_1y_2$ (cf.
Definition~\ref{def:minimal_alternating_path}).
%\COMMENT{Recall, in our definition of minimal, we also include the fact that the edges to be augmented have a weight at least $\gamma$ times the weight of edges to be deleted.}
%maximizes $r(A) := w(A) - \gamma \cdot w(M(A))$
Let this path have vertices $\{b_k, a_k, b_{k-1}, a_{k-1}, \ldots,
b_1, a_1=y_1, y_2=c_1, d_1, c_2, d_2, \ldots, c_{k'}, d_{k'}\}$.
%$\{p_1, q_1, p_2, q_2, \ldots, p_k, q_k=y_1, y_2=d_j, b_j, \ldots, d_2, b_2, d_1, b_1\}$.

\STATE Find the largest $r$ such that $1\leq r\leq k$ and
$\sum_{i=r}^{k-1}{w(b_i,a_{i+1})}\geq
\gamma\cdot\sum_{i=r}^{k}{w(a_i,b_i)}$. Similarly, find the largest
$r'$ such that $1\leq r'\leq k'$ and
$\sum_{i=r'}^{k'-1}{w(d_{i},c_{i+1})}\geq
\gamma\cdot\sum_{i=r'}^{k'}{w(c_{i},d_{i})}$.\\
Let $Q_1$ and $Q_2$ be the sub-paths of $Q$ induced by $\{a_r, b_r,
a_{r+1}, b_{r+1}, \ldots, b_k, a_k\}$ and $\{c_{r'}, d_{r'},
c_{r'+1}, d_{r'+1}, \ldots, c_{k'}, d_{k'}\}$, respectively.

%Set $Q_1 = \{b_k, a_k, \ldots, b_r, a_r\}$ for the largest $1\leq
%r\leq k$ (if such an $r$ exists) such that
%$\sum_{i=r}^{k-1}{w(b_i,a_{i+1})}\geq
%\gamma\cdot\sum_{i=r}^{k}{w(a_i,b_i)}$ and for every  $j\geq r$,
%$\sum_{i=j}^{k-1}{w(b_i,a_{i+1})}\geq
%\gamma\cdot\sum_{i=j+1}^{k}{w(a_i,b_i)}$.\\
%%
%Similarly, set $Q_2 = \{d_{k'}, c_{k'}, \ldots, d_{r'}, c_{r'}\}$
%for the largest $1\leq r'\leq k'$ (if such an $r'$ exists) such that
%$\sum_{i=r'}^{k'-1}{w(d_{i},c_{i})}\geq
%\gamma\cdot\sum_{i=r'}^{k'}{w(c_{i},d_{i})}$ and for every  $j\geq
%r'$, $\sum_{i=j}^{k-1}{w(d_i,c_{i+1})}\geq
%\gamma\cdot\sum_{i=j+1}^{k}{w(c_i,d_i)}$.

%Similarly, set $Q_2 = \{b_1, d_1, \ldots, b_r, d_r\}$ for the smallest $r\leq j$ such that $\sum_{i=1}^{r-1}{w(d_i,b_{i+1})}\geq \gamma\cdot\sum_{i=1}^{r}{w(d_r,b_r)}$, if such an $r\leq j$ exists.

\STATE \label{alg:change_part} If any one of such $r$ and $r'$ does
not exist, then set $r=r'=0$ and let $b_0=c_1$ and $d_0=a_1$.
(Recall that $c_1 = y_2$ and $a_1 = y_1$.)
%Let $M(Q_i)$ denote the matched edges of
%$Q_i$ and $S(Q_i)$ denote the shadow edges of $Q_i$.

\STATE For any $r\leq i \leq k$, remove $a_ib_i$ from $M$. For any
$r\leq i\leq k-1$, add $b_ia_{i+1}$ to $M$ and set shadow-edge($b_i,
a_{i+1}, b_i$)=$a_ib_i$ and shadow-edge($b_ia_{i+1},
a_{i+1}$)=$a_{i+1}b_{i+1}$.\\
%
Similarly, for any $r'\leq i \leq k'$, remove $c_id_i$ from $M$. For
any $r'\leq i\leq k'-1$, add $d_ic_{i+1}$ to $M$ and set
shadow-edge($d_i, c_{i+1}, d_i$)=$c_id_i$ and
shadow-edge($d_ic_{i+1}, c_{i+1}$)=$c_{i+1}d_{i+1}$.
%
%Store each matched edge in $Q_1$ and $Q_2$ as a shadow-edge of its adjacent
%edges in $Q_1$ and $Q_2$ respectively.
%
%For example, if $a_ib_i$ is in $M(Q_1)$ then it becomes a shadow-edge of $b_ia_{i+1}$ and $b_{i-1}a_i$ if these are in $S(Q_1)$. Similarly, in $Q_2$, $c_id_i$ becomes a shadow-edge of $d_ic_{i+1}$ and $d_{i-1}c_i$. (here $b_0=y_2$ and $d_0=y_1$).

%\STATE Update $M$ to delete previously matched edges in $Q_1$ and $Q_2$ and add previous shadow-edges in $Q_1$ and $Q_2$. That is, $M := (M \setminus M(Q_1) \setminus M(Q_2)) \cup S(Q_1) \cup S(Q_2)$.

%\ENDIF
%
\ENDWHILE
\end{algorithmic}
\end{algorithm}

\begin{figure}
\includegraphics[width=\linewidth]{algo.eps}
\caption{Visualization of Algorithm~\ref{alg:shadow_algorithm}}
\label{fig:algo}
\end{figure}
